ABC 243 D - Moves on Binary Tree

提出

code: python

n, x = map(int,input().split())

s = input()

# ライブラリがある...?

# 完全二分木は固定だから...

解答

code: python

n, x = map(int,input().split())

s = list(input())

t = []

# いまいる頂点の番号を保持しながら、移動をそのままシミュレートしようとすると、頂点の番号の桁数が非常に大きくなるためTLE

# L または R の直後に U がある場合、この2回の移動で元の頂点に戻るため、このような移動は無視してもよい

for move in s:

t.pop()

else:

t.append(move)

# 「0 個以上の U からなる文字列」の後ろに「0 個以上の L または R からなる文字列」を連結したものが残る

# print(t)

# 頂点番号が max(最初にいる頂点,最後にいる頂点) を超えることはない

for move in t:

if move == "U": x = x//2

if move == "L": x = x*2

if move == "R": x = x*2+1

print(x)

テーマ

メモ

提出

TLE

code: python

n, x = map(int, input().split())

s = list(input())

# U -> x // 2

# R -> x * 2 + 1

# L -> x * 2

for move in s:

if move == "U":

x //=2

elif move == "R":

x *= 2

x += 1

else:

x *= 2

print(x)

# ランレングス圧縮するにしても最大 O(pow(10, 6))